package algorithm.t202110;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Set;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/10/22 8:27
 * @description :3道
 * 醉酒当歌思故人。
 * persevere to last
 * 2021.10.22
 */
public class t20211022 {

    //229.求众数
    public List<Integer> majorityElement(int[] nums) {
        ArrayList<Integer> res = new ArrayList<>();
        if (res == null) {
            return res;
        }
        int len = nums.length;
        if (len == 1) {
            res.add(nums[0]);
            return res;
        }

        int count = len / 3;

        HashMap<Integer, Integer> map = new HashMap<>();//k为元素，v为出现的次数


        //将每个元素及其映射的出现次数放入map
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
                map.put(nums[i], 1);
            }

        }

        //遍历map，将满足条件的元素放入res
        Set<Integer> keySet = map.keySet();
        for (Integer integer : keySet) {
            if (map.get(integer) > count) {
                res.add(integer);
            }

        }

        return res;

    }

    //70.爬楼梯
    //暴力递归，时间复杂度不通过
    public int climbStairs(int n) {//暴力递归，可以解决问题，但是时间复杂度太高，为O(2^n)
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }


        return climbStairs(n - 2) + climbStairs(n - 1);

    }

    //记忆递归。时间复杂度为O(n)
    public int climbStairs2(int n) {//记忆递归，可以解决时间复杂度问题
        int[] memory = new int[n + 1];

        return find(n, memory);
    }

    private int find(int n, int[] arr) {
        if (arr[n] != 0) {
            return arr[n];
        }

        if (n == 2) {
            arr[n] = 2;
        } else if (n == 1) {
            arr[n] = 1;
        } else {
            arr[n] = find(n - 2, arr) + find(n - 1, arr);

        }

        return arr[n];
    }

    //动态规划
    public int climbStairs3(int n) {

        if (n == 1) {
            return 1;
        }
        int[] dq = new int[n + 1];
        dq[1] = 1;
        dq[2] = 2;
        for (int i = 3; i <= n; i++) {
            dq[i] = dq[i - 1] + dq[i - 2];
        }
        return dq[n];

    }

    //斐波那契数列方式 时间O(n) 空间O(1)
    public int climbStairs4(int n) {
        if (n == 1) {
            return 1;
        }
        int first = 1;
        int second = 2;
        for (int i = 3; i <= n; i++) {
            int third = first + second;
            first = second;//滚动数组
            second = third;
        }

        return second;

    }


    //198.打家劫舍 动态规划问题。
    /*
        步骤1.定义子问题。2.写出子问题的递推关系。3.确定dp数组的计算顺序 4.空间优化（新手不用掌握
     */
    public int rob(int[] nums) {
        if (nums == null) {
            return 0;
        } else if (nums.length == 1) {
            return nums[0];
        }

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);//没选，选了

        }

        return dp[nums.length - 1];

    }


    //120.三角形最小路径和 也是一个动态规划问题。
    int[][] memory;//记忆化数组

    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null) {
            return 0;
        } else if (triangle.size() == 1) {
            return triangle.get(0).get(0);
        }

        memory = new int[triangle.size()][triangle.size()];
        int res = dfs(triangle, 0, 0);
        return res;
    }

    private int dfs(List<List<Integer>> triangle, int x, int y) {
        if (x == triangle.size()) {
            return 0;
        }

        if (memory[x][y] != 0) {
            return memory[x][y];
        }

        memory[x][y] = Math.min(dfs(triangle, x + 1, y), dfs(triangle, x + 1, y + 1)) + triangle.get(x).get(y);

        return memory[x][y];
    }


    public static void main(String[] args) {
        t20211022 t20211022 = new t20211022();
        System.out.println(t20211022.rob(new int[]{2, 7, 9, 3, 1}));

        String x = "fmn";
        String y = x.replace("f", "F");
        y = y + "xyz";


    }

}
